Autor obrázku: Chris Martin http://en.wikipedia.org/wiki/User:Booyabazooka

Kombinatorické myšlení

Kombinatorika trochu jinak

Binomická věta

diskuze, ke stažení v PDF: zadání

Řekneme, že letecká síť je

úplná, pokud jsou každá dvě města spojena linkou v obou směrech.
poloúplná, pokud lze města rozdělit do dvou stejně velkých skupin tak, že linky spojují právě města z různých skupin a to v obou směrech.

okružní, pokud lze města očíslovat

$1$ ,

$2$ , …,

$n$ tak, že jednosměrné linky vedou z

$1$ do

$2$ , z

$2$ do

$3$ , a tak dále až nakonec i z

$n-1$ do

$n$ a z

$n$ do

$1$ , přičemž jiné linky neexistují.

severojižní, pokud lze města očíslovat

$1$ ,

$2$ , …,

$n$ tak, že jednosměrné linky vedou z měst s nižším číslem do měst s vyšším číslem, přičemž jiné linky neexistují.

Úloha č. 1

Určete, kolik linek se nachází mezi $10$ městy, jsou-li spojena

(a) úplnou leteckou sítí
(b) poloúplnou leteckou sítí
(c) okružní sítí
(d) severojižní sítí

Výsledek: (skrýt)

${10 \choose 2} = \frac{10\cdot9}{2} = 45$ obousměrných linek
$5\cdot5=25$ obousměrných linek
$10$
$9+8+7+6+5+4+3+2+1 = {10 \choose 2} = 45$ jednosměrných linek

Výsledek

Řešení: (skrýt)

Mezi každými dvěma městy vede obousměrná linka. Počet obousměrných linek je tak dvojic měst a těch je ${10 \choose 2} = 45$ .
Lze počítat i tak, že z každého z $10$ měst vede $9$ obousměrných linek. Pak ale každou linku započítáme dvakrát („z obou jejích konců“). Odtud $\frac{10\cdot9}{2}$ .
Pěti městům z jedné skupiny říkejme červená. Z každého červeného města vede $5$ obousměrných linek do nečervených měst. Tím jsme započítali všechny linky, protože mezi červenými městy, ani mezi nečervenými městy, žádné linky nevedou. Odtud je počet linek $5\cdot5=25$ .
(c) Z každého města vychází přesně jedna (jednosměrná) linka, takže počet linek je stejný jako počet měst.
Mezi každými dvěma městy vede linka (z města s menším číslem do města s větším číslem). Stejně jako v části (a) dostaneme ${10 \choose 2} = 45$ linek, avšak tentokrát jednosměrných.

Řešení

Úloha č. 2

V letecké síti je 10 měst. Určete počet způsobů, kterak lze procestovat všechna města a každé přitom navštívit právě jednou

(a) v úplné letecké síti?
(b) v poloúplné letecké síti?
(c) v okružní síti?
(d) v severojižní síti?

Výsledek: (skrýt)

$10!=3\,628\,800$
$10\cdot5\cdot4\cdot4\cdot3\cdot3\cdot2\cdot2\cdot1\cdot1 = 28\,800$
$10$
$1$

Výsledek

Řešení: (skrýt)

Na začátek cesty můžeme zvolit libovolné z $10$ měst. Jako druhé navštívené město si můžeme vybrat libovolné z $9$ zbývajících měst. Pro třetí navštívené město máme na výběr z $8$ zbývajících, atd. Celkově tak můžeme cestovat $10\cdot9\cdot8\dots2\cdot1=10!=3\,628\,800$ způsoby.
Začít můžeme v libovolném z $10$ měst. Poté lze pokračovat do libovolných $5$ měst z druhé skupiny. Z nich lze pokračovat do libovolného ze $4$ zbývajících měst z první skupiny (vyřadili jsme město, ve kterém jsme začali). Z něj lze opět pokračovat do libovolného ze $4$ zbývajících měst z druhé skupiny (vyřadili jsme město, které jsme navštívili jako druhé), atd. To vede k výpočtu $10\cdot5\cdot4\cdot4\cdot3\cdot3\cdot2\cdot2\cdot1\cdot1 = 28\,800$ .
(c) Jakmile si vybereme město, ve kterém začneme, je už naše cesta jednoznačně daná. Způsobů je tedy přesně tolik, kolik je měst.
Existuje jenom jedna cesta $1\rightarrow2\rightarrow3\rightarrow4\rightarrow5\rightarrow6\rightarrow7\rightarrow8\rightarrow9\rightarrow10$ . Kdybychom se rozhodli jakékoliv město přeskočit, už se do něj nelze vrátit.

Řešení

Úloha č. 3

(Nejde o výsledky, rozdělte podúlohy do skupin. Více.)

Následující úloha se skládá z několika podúloh. Rozdělte podúlohy do několika skupin (může to být i jen jediná skupina) tak, že všechny podúlohy v jedné skupině mají stejný výsledek. Výsledek podúloh v rámci skupiny není nutné určit a není podstatný. Hledejte důvody pro svá rozhodnutí. Skrýt.

V testu je $10$ otázek a každá nabízí odpověď ANO a NE. Kolika způsoby jej lze vyplnit tak, že $7$ krát je vybrána odpověď ANO a $3$ krát odpověd NE?
Hokejové utkání skončilo výsledkem $7:3$ . Kolika způsoby se mohlo skóre vyvíjet?
Metoděj si z každé závorky vybere buď srdíčko, nebo trojlístek (z každé závorky tedy vybere přesně jeden symbol). Kolika způsoby si může vybrat $3$ srdíčka a $7$ trojlístků? Na obrázku jsou naznačeny dva takové výběry.

(d) Kolikrát se objeví člen

$a^7b^3$ při roznásobení výrazu $\underbrace{(a+b)(a+b)(a+b)(a+b)(a+b)(a+b)(a+b)(a+b)(a+b)(a+b)}_{10}?$

(e) Kolika způsoby lze vybrat tříprvkovou podmnožinu z desetiprvkové množiny?

Výsledek: (skrýt)

(a) = (b) = (c) = (d) = (e)

Výsledek

Řešení: (skrýt)

(a) $\Leftrightarrow$ (b) Vstřelení gólu vítězného týmu odpovídá volbě ANO. Vstřelení gólu týmem, který prohrál, odpovídá volbě NE.
(a) $\Leftrightarrow$ (c) Trojlístek odpovídá volbě ANO, srdíčko odpovídá volbě NE.
Člen $a^7b^3$ vzniká v průbehu roznásobování tak, že z některých sedmi závorek vybereme $a$ a ze zbývajících $3$ závorek vybereme $b$ . To je stejné jako když Metoděj ze $7$ závorek vybere trojlístek a ze zbývajících $3$ závorek vybere srdíčko.
Na Metodějův výběr se můžeme dívat také tak, že si z množiny $10$ závorek vybírá podmnožinu $3$ závorek, z nichž si pak vybere srdíčko.

Řešení

Úloha č. 4

(Nejde o výsledky, rozdělte podúlohy do skupin. Více.)

Která z ostatních úloh vás vede k výpočtu $1+2+3+\ldots+(n-2)+(n-1)+n?$
(b) Kolik dvojic vypíše následující program?

$(s,t)$ takových, že

$s,t\in\{1,2,\ldots,n+1\}$ ?

(d) Kolik existuje uspořádaných dvojic

$(s,t)$ , v nichž

$s<t$ a

$s,t\in\{1,2,\ldots,n+1\}$ ?

(e) Kolika způsoby lze vybrat dvě různá čísla z čísel

$1,2,\ldots,n+1$ ?

(f) Která z ostatních úloh vás vede k výpočtu ${n+1 \choose 2}?$

Výsledek: (skrýt)

(a) = (b) = (d) = (e) = (f)

Výsledek

Řešení: (skrýt)

Program v prvním kroku vypíše dvojice $(1,n+1), (2,n+1), (3,n+1), \ldots, (n,n+1)$ . Těch je $n$ . Ve druhém kroku programu je $b=n$ a program vypíše dvojice $(1,n), (2,n), (3,n), \ldots, (n-1,n)$ . To je dalších $n-1$ dvojic. Tímto způsobem program pokračuje a celkem tak vypíše $n+(n-1)+(n-2)+\ldots+3+2+1$ dvojic.
Program postupně vypisuje přesně všechny dvojice, v nichž je první číslo menší než druhé (a obě čísla jsou z množiny $\{1,2,\dots,n+1\}$ ).
(c) Tato část je jiná než ostatní. V porovnání s částí (d) jsou započítány i ty dvojice, ve kterých je první číslo větší než (nebo stejné jako) druhé číslo.
(d) $\Leftrightarrow$ (e) Každý výběr z části (e) určuje přesně jednu uspořádanou dvojici, v níž je první číslo menší než druhé. Naopak i každá uspořádaná dvojice různých čísel určuje, která dvě čísla jsou vybrána.
V části (e) vybíráme dvě různá čísla z čísel $1,2,\ldots,n+1$ , což jde udělat ${n+1 \choose 2}$ způsoby.

Řešení

Úloha č. 5

Kolika způsoby lze do následujícího plánu doplnit obousměrné linky tak, aby každé město bylo spojeno přesně s jedním jiným městem?

Výsledek: (skrýt)

$7\cdot5\cdot3=105$

Výsledek

Řešení: (skrýt)

Úloha je stejná jako rozdělit $8$ lidí do dvojic. Na základě úloh, ve kterých se opravovaly chyby, lze postupovat velmi mnoha způsoby. Ze zmíněných úloh už víme, že $6$ lidí lze rozdělit do dvojic $15$ způsoby.

Zvolíme si teď jedno město, které označíme jako hlavní. Hlavní město lze spojit s dalším městem jedním ze $7$ způsobů. Zbývající města lze rozdělit do dvojic $15$ způsoby. To dává celkem $7\cdot15=105$ způsobů, jak města požadovaným způsobem spojit.

Řešení

Hodiny

Bonusy

Binomická věta

Úloha č. 1

Úloha č. 2

Úloha č. 3

Úloha č. 4

Úloha č. 5